package num268;

/**
 * 268. 丢失的数字
 * 题目：https://leetcode-cn.com/problems/missing-number/
 * 三叶姐题解:  * 三叶姐题解: https://leetcode-cn.com/problems/ugly-number/solution/gong-shui-san-xie-jian-dan-de-fen-qing-k-dlvg/
 *
 * 原地哈希
 */
class Solution3 {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i && nums[i] < n) swap(nums, nums[i], i--);
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }

    void swap(int[] nums, int i, int j) {
        int c = nums[i];
        nums[i] = nums[j];
        nums[j] = c;
    }

    public static void main(String[] args) {
        new Solution3().missingNumber(new int[]{3, 0, 2});
    }
}
